#include <iostream>
using namespace std;

struct node
{ int info;
  node *next;
};

struct List
{ node *first;
  node *last;
  List()
  { first=last=NULL; }
};
  
void push_front(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = L.first;
  if(L.first==NULL) L.first=L.last=t;
  else L.first = t;
}   
  
void push_back(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = NULL;
  if(L.last==NULL) L.first=L.last=t;
  else { L.last->next = t; L.last=t;  }  
}

void append(List &L, node *p)
{ if(L.last==NULL){ L.first=L.last=p;}
  else { L.last->next = p; L.last=p;  }  
}

void show_list(List L)
{ node *p=L.first;
  while(p!=NULL)
  { cout << p->info << " ";
    p = p->next;
  }
  cout << endl;
}    
  


void split(List &R, List &L1, List &L2)
{
  node *p=R.first; 
  int dir=1; 
  
  while(p!=NULL)
  { if(dir==1) append(L1,p); 
    else       append(L2,p);  
    p = p->next;  
    dir = 3-dir;
  }
  
  L1.last->next = NULL;
  L2.last->next = NULL;
  R.first=R.last=NULL;
}


int main()
{ List L1, L2, R;
  
  push_back(R,50);
  push_back(R,40);
  push_back(R,56); 
  push_back(R,34);
  push_back(R,45);
  push_back(R,30);
  push_back(R,20);
  
  show_list(R);
   
  split(R,L1,L2);
  
  show_list(L1);
  show_list(L2);    
     
  return 0;
}    
